/*
 有一个表盘，上面有n个格子，每个格子上有1个数字K，有两个指针，每走到一个格子上，这个格子就会消失，
 然后指针就会以当前格子为起点向左右分别移动格子内数字K的步数，若指针指向的格子均为空，而还有格子没有全部消去，
 则游戏失败。第一次可以走任意位置，格子全部消去则游戏成功。
 
 输入
 11
 4 3 5 3 2 1 5 3 2 4 2
 
 输出
 3 0 7 4 2 8 10 1 9 5 6
 */
package com.yuan.algorithms.arithmetic_2;

import java.util.Arrays;
import java.util.Scanner;

public class 最终幻想13小游戏 {

	static int[] map;
	static int n;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			System.out.println("请输入表盘格子数：");
			n = sc.nextInt();
			map = new int[n];
			int front = 0;// 队首指针
			int rear = 0;// 队尾指针
			System.out.println("请输入表盘内格子的数字：");
			for (int i = 0; i < map.length; i++) {
				map[i] = sc.nextInt();
			}
			int[] temp = Arrays.copyOf(map, n);
			int[] result = new int[n];
			for (int i = 0; i < temp.length; i++) {
				front = (i + temp[i]) % n;
				rear = (i - temp[i] + n) % n;
				int tI = temp[i];
				result[0] = i;
				temp[i] = 0;
				f(temp, result, front, rear, 1);
				front = 0;
				rear = 0;
				temp = Arrays.copyOf(map, n);
			}
		}
	}

	private static void f(int[] temp, int[] result, int front, int rear, int s) {
		if (s == n) {
			for (int i : result) {
				System.out.print(i+"["+map[i] + "] ");
			}
			System.out.println();
			return;
		}
		if(temp[front]!=0){
			result[s] = front;
			int newRear = (front - temp[front] + n) % n;
			int newFront = (front + temp[front]) % n;
			int g = temp[front];
			temp[front] = 0; 
			f(temp, result, newFront, newRear, s+1);
			temp[front] = g;
		}
		if(temp[rear]!=0){
			result[s] = rear;
			int newFront = (rear + temp[rear]) % n;
			int newRear = (rear - temp[rear] + n) % n;
			int g = temp[rear];
			temp[rear] = 0;
			f(temp, result, newFront, newRear, s+1);
			temp[rear] = g;
		}
	}

}
